Nhà thờ Saint-Eustache được xây dựng để thay thế cho nhà thờ nhỏ, vốn thờ thánh Agnès, ở khu Les Halles. Vào thời kỳ đó, Les Halles là khu phố giàu có nhất của Paris. Nhà thờ mới được mang tên vị thánh Saint Eustache của La Mã.

Ngày 9 tháng 8 năm 1532, Jean de La Barre, quan thái thú Paris đặt viên đá đầu tiên. Kiến trúc sư thiết kế là Pierre Le Mercier đã lấy cảm hứng từ nhà thờ Đức Bà. Pierre Le Mercier bắt đầu công trình ở điện thờ phía Bắc. Trong những năm 1540, mặt trước phía Nam được xây dựng và đầu thế kỷ 17 tiếp đến điện chính. Công việc tiếp tục với hai kiến trúc sư Charles David và François Petit và được cá nhân Jean-Baptiste Colbert tài trợ. Tới năm 1637, nhà thờ Saint-Eustache được làm lễ thánh hóa.

Xây dựng trong hơn một thế kỷ, nhà thờ Saint-Eustache bị ảnh hưởng bởi cả hai phong cách kiến trúc: Gothic và Phục Hưng. Mặt chính phía trước chưa hoàn toàn hoàn thành, đã bị phá vào năm 1754. Mười năm sau, nó được làm mới mang kiến trúc Baroque của kiến trúc sư Hardouin-Mansart de Jouy.

Trong thời kỳ Cách mạng Pháp, từ năm 1793 nhà thờ bị đóng cửa rồi được sử dụng cho mục đích khác. Tới năm 1803, công trình mới quay trở lại thành nhà thờ tôn giáo. Năm 1844, một vụ cháy đã làm tổn hại nghiêm trọng đến nhà thờ, phá hủy dàn đàn ống và ba gian giữa. Sau đó, công trình được kiến trúc sư Victor Baltard cho sửa chữa lại.